#leetcode题目64：最小 路径和
#难度：中等
#时间复杂度：O(m*n)
#空间复杂度：O(m*n)
#方法：动态规划

from typing import List
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:

        if not grid:
            return 0
        m=len(grid)
        n=len(grid[0])
        dp=[[0]*n for _ in range(m)]

        dp[0][0]=grid[0][0]
        for i in range(1,m):
            dp[i][0]=dp[i-1][0]+grid[i][0] #更新第一列
        for j in range(1,n):
            dp[0][j]=dp[0][j-1]+grid[0][j] #更新第一行

        for i in range(1,m):
            for j in range(1,n):
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j] #状态转移方程
        return dp[-1][-1]

#测试数据
grid=[[1,3,1],[1,5,1],[4,2,1]]
#预期输出：7
solution=Solution()
print(solution.minPathSum(grid))

grid=[[1,2,3],[4,5,6]]
#预期输出：12
solution=Solution()
print(solution.minPathSum(grid))
